package com.zjsru.oneDay;

/**
 * 3202. 找出有效子序列的最大长度 II
 *
 * @Author: cookLee
 * @Date: 2025-07-17
 */
public class MaximumLength {

    /**
     * 主
     * \
     * 给你一个整数数组 nums 和一个 正 整数 k 。
     * nums 的一个 子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列 ：
     * <p>
     * (sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k
     * 返回 nums 的 最长有效子序列 的长度。
     * \
     * 输入：nums = [1,2,3,4,5], k = 2
     * 输出：5
     * 解释：
     * 最长有效子序列是 [1, 2, 3, 4, 5] 。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        MaximumLength maximumLength = new MaximumLength();
        System.out.println(maximumLength.maximumLength(new int[]{1, 2, 3, 4, 5}, 2));
    }

    public int maximumLength(int[] nums, int k) {
        int ans = 0;
        int[][] dp = new int[k][k];
        for (int num : nums) {
            num %= k;
            for (int i = 0; i < k; i++) {
                // 更新 dp[i][num]：表示在以 num 结尾的子序列前添加当前数（模 k 后为 num）， 长度增加 1
                dp[i][num] = dp[num][i] + 1;
                ans = Math.max(ans, dp[i][num]);
            }
        }
        return ans;
    }

}
